package 中等.模拟;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，
 * 从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第
 * n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
 * 游戏遵循如下规则：
 * 从第 1 名小伙伴所在位置 开始 。
 * 沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
 * 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
 * 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
 * 否则，圈子中最后一名小伙伴赢得游戏。
 * 给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game
 */
public class 找出游戏的获胜者_1823 {

    public static void main(String[] args) {

        // 1 2 3 4 5 6
        // f(6,5) = 0
        // 6 1 2 3 4
        // f(6,5) = (f(5,6)+k)%6
        System.out.println(findTheWinner2(5, 2));

    }

    /**
     * 使用一个双端队列进行模拟
     *
     * @param n
     * @param k
     * @return
     */
    public static int findTheWinner(int n, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            deque.addLast(i);
        }
        while (deque.size() != 1) {
            for (int i = 0; i < k - 1; i++) {
                deque.addLast(deque.pollFirst());
            }
            deque.pollFirst();
        }
        return deque.peekFirst();
    }

    /**
     * 约瑟夫环公式
     * f(n,k) = (f(n-1,k)+k)%n
     * <p>
     * 0 1 2 3 4
     * 1 2 3 4 5
     * 3 4 5 1
     * 5 1 3
     * 3 5
     * 3
     * f(1,2) = 0  剩下一个人是胜利者索引0的位置
     * f(2,2) = (f(1,2)+2)%2 = 0  剩下两个人时胜利者为索引0的位置
     * f(3,3) = (f(2,2)+2)%3 = 2  剩下三个人时胜利者为索引2的位置
     * ...
     *
     * @param n
     * @param k
     * @return
     */
    public static int findTheWinner2(int n, int k) {
        // f(1,k)==0
        int winner = 0;
        for (int i = 2; i <= n; i++) {
            winner = (winner + k) % i;
        }
        return winner + 1;
    }

}
